#include <queue>
#include <tuple>

using namespace std;

class Solution {
private:
    inline int sum(int n1, int n2) {
        int sum = 0;
        while (n1 > 0) {
            sum += n1 % 10;
            n1 /= 10;
        }
        while (n2 > 0) {
            sum += n2 % 10;
            n2 /= 10;
        }
        return sum;
    }
public:
    int movingCount(int m, int n, int k) {
        vector<vector<int>> visited(m, vector<int>(n, false));
        queue<tuple<int, int>> queue;
        queue.push(make_tuple(0, 0));
        visited[0][0] = true;
        int ans = 0;
        while (queue.size() > 0) {
            ans++;
            tuple<int, int>& pos = queue.front();
            int& i = get<0>(pos);
            int& j = get<1>(pos);
            if (i > 0 && !visited[i - 1][j]) {
                visited[i - 1][j] = true;
                if (sum(i - 1, j) <= k) {
                    queue.push(make_tuple(i - 1, j));
                }
            }
            if (i < m - 1 && !visited[i + 1][j]) {
                visited[i + 1][j] = true;
                if (sum(i + 1, j) <= k) {
                    queue.push(make_tuple(i + 1, j));
                }
            }
            if (j > 0 && !visited[i][j - 1]) {
                visited[i][j - 1] = true;
                if (sum(i, j - 1) <= k) {
                    queue.push(make_tuple(i, j - 1));
                }
            }
            if (j < n - 1 && !visited[i][j + 1]) {
                visited[i][j + 1] = true;
                if (sum(i, j + 1) <= k) {
                    queue.push(make_tuple(i, j + 1));
                }
            }
            queue.pop();
        }
        return ans;
    }
};